
/*
* Copyright 2009, Center for Advanced Information Systems,Nanyang Technological University
*
* File name: Allsubgraph.java
*
* Abstract: Get all the subgraphs of a given graph
*
* Current Version:      0.1
* Auther:               Jin Changjiu
* Modified Date:        Jun.16,2009
*
*/
/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package gblend.infrequentindex;

import gblend.adjlistgraph.ALGraph;
import java.util.Collections;
import java.util.HashSet;
import java.util.Vector;
import gblend.frequentindex.Vertex;


/**
 *
 * @author cjjin
 */
public class Allsubgraph {
private static BuildCam bc = new BuildCam();


 public  Vector<String> getSubgraphCam(ALGraph graph)
 {
    HashSet<String> subcams = new HashSet<String>();
    getAllSubgraph(graph,subcams);
    Vector<String> list = new Vector<String>();

    for(String value : subcams){
       list.addElement(value);
    }
    
    StringSort ss = new StringSort();
    Collections.sort(list,ss);
    list.addElement(bc.buildCam(graph));//add the graph itself

    return list;
   
 }


 public HashSet<String> getAllSubgraph(ALGraph graph,HashSet<String> subcam)
 {
      int gsize = graph.getNnum();

      for(int i = 0;i<gsize-1;i++)//delete one node,not the last one
      {
            ALGraph subgraph = new ALGraph(gsize-1);
            subgraph.setNnum(gsize-1);
            for(int j= 0;j<gsize;j++)
            {
                if(j!=i)
                {
                    Vertex node = new Vertex();
                    node.setLabel(graph.getNode(j).getLabel());
                    subgraph.addnode(node);

                    for(int k= 0;k<gsize;k++)
                    {
                        if(k!=i&&graph.getEdge(j, k)==1)
                        {
                            int m = 0,n=0;
                            if(j>i)
                            {
                                m = j-1;
                            }
                            else
                            {
                                m = j;
                            }
                             if(k>i)
                            {
                                n = k-1;
                            }
                            else
                            {
                                n = k;
                            }

                           subgraph.addEdge(m, n);
                           subgraph.getNode(m).setDegree();
                           subgraph.getNode(m).setId(m);
                        }

                    }
                }

            }

            int k = 0;
            for(k=0;k<gsize-1;k++)
            {
                if(subgraph.getNode(k).getDegree()==0)
                {
                     break;
                }
            }
            if(k==gsize-1)
            {
                getAllSubgraph(subgraph,subcam);
                String subcamstr = bc.buildCam(subgraph);
                subcam.add(subcamstr);
            }
        }

       
        return subcam;
 }


}
